"""  """
from typing import List

# 位运算 i&(i-1) 可以把最小位的1变0

def countBits(n: int) -> List[int]:
    def get_count(i):
        """ count = 0
        while i:
            i=i&(i-1)
            count += 1
        return count

    return [get_count(i) for i in range(n+1)] """
    res = [0]
    high = 0 
    for i in range(n+1):
        if i&(i-1) == 0: # 被2整除，即为最高位
            high = i
        res.append(res[i - high]+1)
    return res


